package com.lucien.Recursion;

public class MiGong {
    public static void main(String[] args) {
        //创建一个二维数组，模拟迷宫
        int[][] map = new int[8][7];
        //使用1 代表墙
        //将上下全部置为1
        for (int i = 0; i < 7; i++) {
            map[0][i] = 1;
            map[7][i] = 1;
        }
        //将左右全部置为1
        for (int i = 0; i < 8; i++) {
            map[i][0] = 1;
            map[i][6] = 1;
        }
        map[3][1] = 1;
        map[3][2] = 1;


        //输出地图
        for (int i = 0; i < 8; i++) {
            for (int j = 0; j < 7; j++) {
                System.out.print(map[i][j] + " ");
            }
            System.out.println();
        }

//        setWay(map,1,1);
        setWay2(map, 1, 1);
        System.out.println("找到出路后的地图");
        for (int i = 0; i < 8; i++) {
            for (int j = 0; j < 7; j++) {
                System.out.print(map[i][j] + " ");
            }
            System.out.println();
        }
    }

    //使用递归回溯来给小球找路

    /**
     * 说明：
     * 1、map表示地图
     * 2、i，j表示从地图的哪个位置开始出发
     * 3、如果小球能找到map[6][5] 的位置，说明找到出路
     * 4、约定：当map[i][j] 为0时表示该点没有走过；为1时表示墙；
     * 为2时表示通路可以走；为3表示该点走过，但是不通
     * 5、在走迷宫时，需要定一个策略(方法)，下->右->上->左,如果该点走不通，在回溯
     *
     * @param map 表示地图
     * @param i   表示从哪个位置开始找
     * @param j
     * @return 如果找到通路返回true，没有则返回false；
     */
    public static boolean setWay(int[][] map, int i, int j) {
        if (map[6][5] == 2) {//已经找到通路
            return true;
        } else {
            if (map[i][j] == 0) {//如果当前这个点还没有走过
                //按照策略 下->右->上->左
                map[i][j] = 2;//假定该点可以走通
                if (setWay(map, i + 1, j)) {//向下走
                    return true;
                } else if (setWay(map, i, j + 1)) {//向右走
                    return true;
                } else if (setWay(map, i - 1, j)) {//向上走
                    return true;
                } else if (setWay(map, i, j - 1)) {//向左走
                    return true;
                } else {
                    map[i][j] = 3;//说明该点是死了路，走不通
                    return false;
                }
            } else {//如果map[i][j] ！= 0，可能为1，2，3
                return false;
            }
        }
    }

    public static boolean setWay2(int[][] map, int i, int j) {
        if (map[6][5] == 2) {//已经找到通路
            return true;
        } else {
            if (map[i][j] == 0) {//如果当前这个点还没有走过
                //按照策略 上->右->下->左
                map[i][j] = 2;//假定该点可以走通
                if (setWay2(map, i - 1, j)) {//向上走
                    return true;
                } else if (setWay2(map, i, j + 1)) {//向右走
                    return true;
                } else if (setWay2(map, i + 1, j)) {//向下走
                    return true;
                } else if (setWay2(map, i, j - 1)) {//向左走
                    return true;
                } else {
                    map[i][j] = 3;//说明该点是死了路，走不通
                    return false;
                }
            } else {//如果map[i][j] ！= 0，可能为1，2，3
                return false;
            }
        }
    }
}
